/*
Combinations
Given two integers n and k, return all possible combinations of k numbers out of 1 ... n.

For example,
If n = 4 and k = 2, a solution is:

[
[2,4],
[3,4],
[2,3],
[1,2],
[1,3],
[1,4],
]
*/
#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

class Solution {
public:

	void combine_rec(vector<vector<int> > &result, vector<int> &temp, int n, int k, int index)
	{
		if (k == 0)
		{
			result.push_back(temp);
			return;

		}
		else if (k > 0 && index <= n)
		{
			temp.push_back(index);
			combine_rec(result, temp, n, k - 1, index + 1);

			temp.pop_back();
			combine_rec(result, temp, n, k, index + 1);

		}
	}
	vector<vector<int>> combine(int n, int k) {
		vector<vector<int>> result;
		vector<int> temp;
		combine_rec(result, temp, n, k, 1);

		return result;

	}
};

int main()
{
	cout << "Combination " << endl;
	
	int k, n;
	cin >> k >> n;
	Solution s;

	vector<vector<int> > result;
	result = s.combine(n, k);

	cout << "result:" << endl;

	for (int i = 0; i < result.size(); i++)
	{
		for (int j = 0; j < result[j].size(); j++)
		{
			cout << result[i][j]<< " ";
		}
		cout << endl;
	}

	system("pause");

	return 0;
}